/*
 * gx_rbtree.c
 *
 *  Created on: 2012-3-11
 *      Author: zhangguanxing
 *      Description:
 */
#include <stdlib.h>
#include <stdio.h>

#include "gx.h"
#include "gx_rbtree.h"
typedef struct r_gx_rbtree_node r_gx_rbtree_node_t; //real node of rbtree

#define RBTREE_BLACK 0
#define RBTREE_RED	 1

struct r_gx_rbtree_node {
	//user visible value
	gx_rbtree_node_t key_node;

	//invisible value
	int color;
	r_gx_rbtree_node_t* left, *right, *parent;
};

#define node_is_red(node) ((node)->color == RBTREE_RED)
#define node_is_black(node) ((node)->color == RBTREE_BLACK)

#define is_sentinel(rnode, sentinel) ((rnode) == (r_gx_rbtree_node_t *)(sentinel))

static void
gx_rbtree_left_rotate(gx_rbtree_t* tree, r_gx_rbtree_node_t* node){
	r_gx_rbtree_node_t* pnode;

	pnode = node->right;
	node->right = pnode->left;

	if(is_sentinel(pnode, tree->sentinel))
		return;

	if (!is_sentinel(pnode->left ,tree->sentinel)) {
		pnode->left->parent = node;
	}

	pnode->parent = node->parent;
	if (is_sentinel(pnode->parent,tree->sentinel)) {
		tree->root = (gx_rbtree_node_t *)pnode;
	}
	else {
		if (node->parent->left == node){
			node->parent->left = pnode;
		}
		else {
			node->parent->right = pnode;
		}
	}
	pnode->left = node;
	node->parent= pnode;
}
static void
gx_rbtree_right_rotate(gx_rbtree_t* tree, r_gx_rbtree_node_t* node){
	r_gx_rbtree_node_t* pnode;

	if(is_sentinel(pnode, tree->sentinel))
		return;
	pnode = node->left;
	node->left = pnode->right;

	if (!is_sentinel(pnode->right,tree->sentinel)) {
		pnode->right->parent = node;
	}
	pnode->parent = node->parent;
	if (is_sentinel(pnode->parent ,tree->sentinel)) {
		tree->root = (gx_rbtree_node_t *)pnode;
	}
	else {
		if (node->parent->right == node){
			node->parent->right = pnode;
		}
		else {
			node->parent->left = pnode;
		}
	}
	pnode->right = node;
	node->parent= pnode;
}

static void
default_cpy_func(gx_rbtree_node_t *a, gx_rbtree_node_t *b) {
	a->key = b->key;
	a->usr_data = b->usr_data;
}

static int
default_cmp_func(gx_rbtree_key_t a, gx_rbtree_key_t b) {
	if (a > b)
		return 1;
	else if (a == b)
		return 0;
	else
		return -1;
}

int
gx_rbtree_init(gx_rbtree_t* tree) {
	assert(tree);

	tree->sentinel = (gx_rbtree_node_t*)gx_malloc(sizeof(r_gx_rbtree_node_t));
	((r_gx_rbtree_node_t *)(tree->sentinel))->color = RBTREE_BLACK;
	((r_gx_rbtree_node_t *)(tree->sentinel))->parent = NULL;
	((r_gx_rbtree_node_t *)(tree->sentinel))->left = (r_gx_rbtree_node_t *)(tree->sentinel);
	((r_gx_rbtree_node_t *)(tree->sentinel))->right = (r_gx_rbtree_node_t *)(tree->sentinel);
	tree->root = tree->sentinel;
	tree->size = 0;
	return 0;
}


static void
fixup_delete(gx_rbtree_t* tree, r_gx_rbtree_node_t* node) {
	r_gx_rbtree_node_t *pnode;
	// move node up to a red node or node is root itself
	while(node != (r_gx_rbtree_node_t *)(tree->root) &&
		  node_is_black(node)){
		if (node == node->parent->left) {
			//node is left child of his parent
			pnode= node->parent->right; //pnode is brother of node
			if(node_is_red(pnode)){
				// brother is red, just rotate and re draw color
				pnode->color = RBTREE_BLACK;
				node->parent->color = RBTREE_RED;
				gx_rbtree_left_rotate(tree, node->parent);
				pnode = node->parent->right;
			}
			//now his brother is definitely black
			if(node_is_black(pnode->left) && node_is_black(pnode->right)){
				pnode->color = RBTREE_RED;
				node = node->parent;
			}
			else {
				if (node_is_black(pnode->right)){
					pnode->color = RBTREE_RED;
					pnode->left->color = RBTREE_BLACK;
					gx_rbtree_right_rotate(tree, pnode);
					pnode = node->parent->right;
				}

				pnode->color = node->parent->color;
				node->parent->color = RBTREE_BLACK;
				pnode->right->color = RBTREE_BLACK;
				gx_rbtree_left_rotate(tree, node->parent);
				node = (r_gx_rbtree_node_t *)(tree->root);
			}
		}

		else{
			//node is right child of his parent
			pnode= node->parent->left; //pnode is brother of node
			if(node_is_red(pnode)){
				// brother is red, just rotate and re draw color
				pnode->color = RBTREE_BLACK;
				node->parent->color = RBTREE_RED;
				gx_rbtree_right_rotate(tree, node->parent);
				pnode = node->parent->left;
			}
			//now his brother is definitely black
			if(node_is_black(pnode->right) && node_is_black(pnode->left)){
				pnode->color = RBTREE_RED;
				node = node->parent;
			}
			else {
				if (node_is_black(pnode->left)){
					pnode->color = RBTREE_RED;
					pnode->right->color = RBTREE_BLACK;
					gx_rbtree_left_rotate(tree, pnode);
					pnode = node->parent->left;
					}

				pnode->color = node->parent->color;
				node->parent->color = RBTREE_BLACK;
				pnode->left->color = RBTREE_BLACK;
				gx_rbtree_right_rotate(tree, node->parent);
				node = (r_gx_rbtree_node_t *)(tree->root);
			}
		}
	}
	//set pnode color to black
	node->color = RBTREE_BLACK;
}

static void
fixup_insert(gx_rbtree_t* tree, r_gx_rbtree_node_t* node){
	r_gx_rbtree_node_t* pnode;

	while (node != (r_gx_rbtree_node_t *)(tree->root)
		   && node_is_red(node->parent))
	{
		if (node->parent == node->parent->parent->left) {
			//			(BLACK)
			//			/	  \
			//		   /	   \
			//		(RED)		(RED)
			//		/
			//     /
			//	  node(RED)
			// just redraw colors
			pnode = node->parent->parent->right; // pnode is uncle node
			if(node_is_red(pnode)) {
				node->parent->color 		= RBTREE_BLACK;
				node->parent->parent->color = RBTREE_RED;
				pnode->color				= RBTREE_BLACK;
				node = node->parent->parent;
			}
			else {
				if (node == node->parent->right){
					//			(BLACK)
					//			/	\
					//		   /	 \
					//		(RED*)	 (BLACK) uncle is black
					//			\
					//     	     \
					//	  	     node(RED)
					// left rotate around node's parent node
					node = node->parent;
					gx_rbtree_left_rotate(tree, node);
				}

				//			(BLACK)
				//			/	\
				//		   /	 \
				//		(RED)	 (BLACK) uncle is black
				//		/
				//     /
				//	  node(RED)

				node->parent->color = RBTREE_BLACK;
				node->parent->parent->color = RBTREE_RED;
				gx_rbtree_right_rotate(tree, node->parent->parent);
			}//else
		}//if

		else if (node->parent == node->parent->parent->right){
				pnode = node->parent->parent->left; // pnode is uncle node
				if(node_is_red(pnode)) {
					node->parent->color 		= RBTREE_BLACK;
					node->parent->parent->color = RBTREE_RED;
					pnode->color				= RBTREE_BLACK;
					node = node->parent->parent;
				}//if
				else {
					if (node == node->parent->left){
						node = node->parent;
						gx_rbtree_right_rotate(tree, node);
					}
					node->parent->color = RBTREE_BLACK;
					node->parent->parent->color = RBTREE_RED;
					gx_rbtree_left_rotate(tree, node->parent->parent);
				}//else
		}// if
	}//while
	((r_gx_rbtree_node_t *)(tree->root))->color = RBTREE_BLACK;
}//func

int
gx_rbtree_insert(gx_rbtree_t* tree, gx_rbtree_key_t key, void* usr_data) {
	assert(tree);

	//firstly insert as normal binary-search tree
	r_gx_rbtree_node_t* new_r_node = (r_gx_rbtree_node_t*)gx_malloc(sizeof(r_gx_rbtree_node_t));
	r_gx_rbtree_node_t* pnode = (r_gx_rbtree_node_t*)(tree->root), *parent;

	if (!new_r_node)
		return -1;

	tree->size++;
	//create new rbtree node
	new_r_node->key_node.key = key;
	new_r_node->key_node.usr_data = usr_data;

	parent = (r_gx_rbtree_node_t *)(tree->sentinel);

	while (!is_sentinel(pnode, tree->sentinel)) {
		parent = pnode;
		if (default_cmp_func(new_r_node->key_node.key, pnode->key_node.key) == -1) {
			pnode = pnode->left;
		}
		else {
			pnode = pnode->right;
		}
	}//while

	if (is_sentinel(parent,tree->sentinel)){
		//root is NIL
		new_r_node->left = (r_gx_rbtree_node_t *)(tree->sentinel);
		new_r_node->right= (r_gx_rbtree_node_t *)(tree->sentinel);
		new_r_node->parent = (r_gx_rbtree_node_t *)(tree->sentinel);
		new_r_node->color = RBTREE_BLACK;
		tree->root = &(new_r_node->key_node);
		return 0;
	}
	else {
		//now parent point to new nodes's parent
		if (default_cmp_func(new_r_node->key_node.key, parent->key_node.key) == -1) {
			//insert to left
			parent->left = new_r_node;
		}
		else {
			parent->right = new_r_node;
		}
	}

	new_r_node->left = (r_gx_rbtree_node_t *)(tree->sentinel);
	new_r_node->right= (r_gx_rbtree_node_t *)(tree->sentinel);
	new_r_node->parent= parent;

	new_r_node->color = RBTREE_RED;

	fixup_insert(tree, new_r_node);
	return 0;
}

static r_gx_rbtree_node_t*
gx_rbtree_get_successor(gx_rbtree_t* tree, r_gx_rbtree_node_t* node) {
	r_gx_rbtree_node_t* pnode;

	if (is_sentinel(node, tree->sentinel))
		return (r_gx_rbtree_node_t *)(tree->sentinel);

	if(!is_sentinel(node->right,tree->sentinel)){
		//walk to right once then walk through to left side
		pnode = node->right;
		while(!is_sentinel(pnode->left, tree->sentinel)){
			pnode = pnode->left;
		}
		return pnode;
	}
	else {
		pnode = node->parent;
		//walk up to parent until reach NULL
		while(!is_sentinel(pnode, tree->sentinel) &&
			 (pnode->right->key_node.key == node->key_node.key)){
			node = pnode;
			pnode= pnode->parent;
		}
		return pnode;
	}


}

int
gx_rbtree_delete(gx_rbtree_t* tree, gx_rbtree_node_t* node) {
	assert(tree);
	assert(node);

	r_gx_rbtree_node_t* rnode = (r_gx_rbtree_node_t *)node;
	r_gx_rbtree_node_t* successor, *pnode;
	int is_left;

	if(node == tree->sentinel)
		return -1;

	tree->size--;
	//if rnode have just one child, just combine this child to his parent
	if (is_sentinel(rnode-> left, tree->sentinel) ||
		is_sentinel(rnode->right, tree->sentinel)) {
		successor = rnode; //successor is himself
	}
	else {
		successor = gx_rbtree_get_successor(tree, rnode);
	}

	//set pnode to one of none Nil child or Nil if pnode has no child
	pnode = is_sentinel(successor->left,tree->sentinel) ? successor->right : successor->left;

	//if successor has child, combine it to his parent
	pnode->parent = successor->parent;

	//set successor in deleting node position
	if (is_sentinel(successor->parent, tree->sentinel)) {
		//successor is root
		tree->root = (gx_rbtree_node_t*)pnode;
		pnode->color = RBTREE_BLACK;
		pnode->left = pnode->right = pnode->parent
				= (r_gx_rbtree_node_t*)tree->sentinel;
		return 0;
	}
	else {
		//change successor's parents child pointer
		if (successor == successor->parent->left){
			successor->parent->left = pnode;
		}
		else {
			successor->parent->right = pnode;
		}
	}

	if (successor != rnode) {
		//if copy successor to deleting node
		default_cpy_func(&(rnode->key_node) , &(successor->key_node));
	}
	if (successor->color == RBTREE_BLACK) {
		fixup_delete(tree, pnode);
	}

	return 0;
}

static int
gx_rbtree_search_one(gx_rbtree_t* tree, r_gx_rbtree_node_t* root, gx_rbtree_key_t key, gx_array_t* node_list) {
	r_gx_rbtree_node_t* pnode = root;

	while(!is_sentinel(pnode,tree->sentinel)) {
		int result = default_cmp_func(pnode->key_node.key, key);
		if (result == 1) {
			pnode = pnode->left;
		}
		else if (result == -1) {
			pnode = pnode->right;
		}
		else {
			break;
		}
	}

	if (!is_sentinel(pnode,tree->sentinel)){
		gx_rbtree_node_t** new_found_node = (gx_rbtree_node_t**)gx_array_push(node_list);
		*new_found_node = pnode;
		gx_rbtree_search_one(tree, pnode->left, key, node_list);
		gx_rbtree_search_one(tree, pnode->right,key, node_list);
		return 0;
	}
	else {
		return -1;
	}
}

int
gx_rbtree_search(gx_rbtree_t* tree, gx_rbtree_key_t key, gx_array_t* node_list){
	assert(tree);
	assert(node_list);
	assert(gx_array_is_init(node_list));
	assert(node_list->elt_size == sizeof(gx_rbtree_node_t*));

	return gx_rbtree_search_one(tree, (r_gx_rbtree_node_t*)(tree->root), key,
			node_list);
}

int gx_rbtree_minimum(gx_rbtree_t* tree, gx_array_t* node_list){
	r_gx_rbtree_node_t 	*pnode = (r_gx_rbtree_node_t *)(tree->root);

	while(!is_sentinel(pnode->left, tree->sentinel)){
		pnode = pnode->left;
	}

	if(!is_sentinel(pnode, tree->sentinel)){
		gx_rbtree_search(tree, pnode->key_node.key, node_list);
	}

	return 0;
}

//found a node 'just' big than key, if key is larger than biggest, just return smallest node
int gx_rbtree_search_nearest(gx_rbtree_t* tree, gx_rbtree_key_t key, gx_array_t* node_list){
	assert(tree);
	assert(node_list);
	assert(gx_array_is_init(node_list));
	assert(node_list->elt_size == sizeof(gx_rbtree_node_t*));
	//virtual 'insert'
	r_gx_rbtree_node_t *pnode = (r_gx_rbtree_node_t*)(tree->root), *parent, *successor;
	if(is_sentinel(pnode, tree->sentinel)){
		return -1;
	}

	parent = pnode->parent; //sentinel
	while(!is_sentinel(pnode, tree->sentinel)){
		parent = pnode;
		int cmp_ret = default_cmp_func(pnode->key_node.key, key);
		if(cmp_ret == 1) {
			pnode = pnode->left;
		}
		else{
			pnode = pnode->right;
		}
	}

	//now parent point to virtual parent who is leaf or one child node actually
	if(default_cmp_func(parent->key_node.key, key) == 1){
		//left child of parent
		//now successor is parent
		successor = parent;
	}
	else{
		//right child of parent
		//walk up until root's father
		pnode = parent;
		parent = parent->parent;

		int cmp_result  = default_cmp_func(parent->key_node.key, pnode->key_node.key);
		while(!is_sentinel(parent, tree->sentinel) &&
			  (default_cmp_func(parent->key_node.key, pnode->key_node.key) == -1)){
			pnode = parent;
			parent = parent->parent;
		}
		successor = parent;
	}

	if(is_sentinel(successor, tree->sentinel)){
		//no successor
		gx_rbtree_minimum(tree, node_list);
	}
	else{
		gx_rbtree_search(tree, successor->key_node.key, node_list);
	}

	return 0;
}

static void
recurse_print_rbtree(gx_rbtree_t* tree, r_gx_rbtree_node_t* pnode) {
	assert(tree);
	assert(pnode);

	if (is_sentinel(pnode, tree->sentinel))
		return;
	else {
		printf("key %d , my parent: key %d. my color is %s\n",
				pnode->key_node.key,
				is_sentinel(pnode->parent,tree->sentinel)? -1 : pnode->parent->key_node.key,
				pnode->color == RBTREE_RED? "red": "black");
		recurse_print_rbtree(tree, pnode->left);
		recurse_print_rbtree(tree, pnode->right);
	}
}

void
print_rbtree(gx_rbtree_t* tree) {
	r_gx_rbtree_node_t* root = (r_gx_rbtree_node_t *)(tree->root);
	recurse_print_rbtree(tree, root);
}

static int
check_tree_color(gx_rbtree_t* tree, r_gx_rbtree_node_t* node){
	if (is_sentinel(node, tree->sentinel))
		return 1;
	if (node->color == RBTREE_RED) {
		if (node_is_black(node->left) &&
			node_is_black(node->right)){
			return check_tree_color(tree, node->left) && check_tree_color(tree, node->right);
		}
		else{
			printf("node %d error\n", node->key_node.key);
			return 0;
		}
	}
	return 1;
}

static int
check_black_path(gx_rbtree_t* tree, r_gx_rbtree_node_t* node) {
	if (is_sentinel(node, tree->sentinel))
		return 1;
	else {
		int left_path = check_black_path(tree, node->left);
		int right_path = check_black_path(tree, node->right);
		if (left_path == -1 || right_path == -1 ||
			left_path != right_path)
		{
			printf("%d node error, left path %d, right path %d\n",
					node->key_node.key,
					left_path,
					right_path);
			return -1;
		}
		return left_path + !node_is_red(node);
	}
}

int
gx_rbtree_check(gx_rbtree_t* tree){
	int result = 0;
	result = check_tree_color(tree, (r_gx_rbtree_node_t*)(tree->root));
	if (!result) {
		printf("color check error\n");
		return -1;
	}
	else {
		//printf("color check right\n");
	}

	result = check_black_path(tree, (r_gx_rbtree_node_t*)(tree->root));
	if(result == -1) {
		printf("black path check error\n");
		return -1;
	}
	else {
		//printf("black path check right\n");
	}
	return 0;
}

static void
recursive_free_node(gx_rbtree_t* tree, r_gx_rbtree_node_t* node){
	if(is_sentinel(node,tree->sentinel))
		return;

	recursive_free_node(tree, node->left);
	recursive_free_node(tree, node->right);

	gx_free(node);
	return;
}
void
gx_rbtree_destroy(gx_rbtree_t* tree){
	r_gx_rbtree_node_t* root = (r_gx_rbtree_node_t*)(tree->root);
	recursive_free_node(tree, root);
	gx_free(tree->sentinel);
}
